package com.zm.demo.core.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;
import java.util.TreeMap;

import static java.lang.System.out;

/**
 * @author zoum
 * @create 2020/1/13 16:52
 */
public class ContainsNearbyAlmostDuplicate {

    public static boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null | nums.length == 0){
            return false;
        }

        Map<Long, Long> map = new HashMap<>();
        int w = t+1;
        for (int i = 0; i < nums.length; i++) {
            long m = getKey(nums[i], w);
            if (map.containsKey(m)){
                return true;
            }else if (map.containsKey(m-1) && Math.abs(nums[i] - map.get(m-1)) < w){
                return true;
            }else if (map.containsKey(m+1) && Math.abs(nums[i] - map.get(m+1)) < w){
                return true;
            }
            map.put(m, (long)nums[i]);
            if ( i >= k){
                map.remove(getKey(nums[i-k], w));
            }
        }
        return false;
    }
    private static long getKey(int x, int w){
        return x < 0 ? (x+1)/w - 1 : x/w;
    }

    public static void main(String[]args){
        out.println(containsNearbyAlmostDuplicate(new int[]{9,8,7,6,5,4,3,2,1,0,19,18,17,16,15,14,13,12,11,10}, 9, 5));
    }

}
class Record{
    int index;
    int value;
    Record(int index, int value){
        this.index = index;
        this.value = value;
    }
}
